package com.cobla.struct.map;

import lombok.*;

/**
 * @ClassName TableMap
 * @Description 邻接表
 * @Author wt
 * @Date 2019/9/8
 * @Version 0.1
 */
@Getter
public class TableMap {
    private final Node[] nodes;
    int n, e;

    public TableMap(int nodeMaxNumber) {
        this.nodes = new Node[nodeMaxNumber];
        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = new Node(i, null);
        }
        this.n = this.nodes.length;
        this.e = 0;
    }

    /**
     * 深度遍历搜索
     * @param startedNodeIndex
     */
    public void DFS(int startedNodeIndex){
        // 已访问过的标记矩阵
        int[] visited = new int[this.n];
        dfs(startedNodeIndex, visited);
    }

    private void dfs(int nodeIndex, int[] visited){
        visited[nodeIndex] = 1;
        visit(nodeIndex);
        Edge p = this.nodes[nodeIndex].getFirstEdge();
        while (p != null) {
            if (visited[p.getNode().getNodeNumber()] == 0) {
                dfs(p.getNode().getNodeNumber(), visited);
            }
            p = p.getNextEdge();
        }
    }

    private void visit(int nodeIndex) {
        System.out.println("访问了 点 "+nodeIndex);
    }

    /**
     *
     * @param startedNodeIndex
     * @param visited
     */
    public void BFS(int startedNodeIndex, int[] visited) {
        int[] que = new int[this.nodes.length];
        int front = 0, rear = 0;

        visited[startedNodeIndex] = 1;
        visit(startedNodeIndex);

        rear = (rear+1) % que.length;
        que[rear] = startedNodeIndex;

        while (front != rear) {
            front = (front + 1) % que.length;
            int index = front;

            Edge p = this.nodes[index].getFirstEdge();
            while (p != null) {
                int indices = p.getNode().getNodeNumber();
                if (visited[indices] == 0) {
                    visited[indices] = 1;
                    visit(indices);
                    rear = (rear+1) % que.length;
                    que[rear] = indices;
                }
            }
            p = p.getNextEdge();

        }
    }

}

@NoArgsConstructor
@Data
class Edge {
    private Node node;
    private Edge nextEdge;
    // 边的信息，例如权值
    private int info;
}

@Data
@NoArgsConstructor
@AllArgsConstructor
class Node {
    /**
     *     点的编号 == 下标
     */
    private int nodeNumber;
    private Edge firstEdge;

    public Node(Edge firstEdge) {
        this.firstEdge = firstEdge;
    }
}
